{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4b1917bf",
   "metadata": {},
   "source": [
    "# 1. 两数之和\n",
    "\n",
    "> 给你一个下标从 **1** 开始的整数数组 `numbers` ，该数组已按 **非递减顺序排列** ，请你从数组中找出满足相加之和等于目标数 `target` 的两个数。如果设这两个数分别是 `numbers[index1]` 和 `numbers[index2]` ，则 `1 <= index1 < index2 <= numbers.length` 。\n",
    ">\n",
    "> 以长度为 2 的整数数组 `[index1, index2]` 的形式返回这两个整数的下标 `index1` 和 `index2`。\n",
    ">\n",
    "> 你可以假设每个输入 **只对应唯一的答案** ，而且你 **不可以** 重复使用相同的元素。\n",
    ">\n",
    "> 目标：$O(n)$\n",
    "\n",
    "[两数之和 三数之和【基础算法精讲 01】_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1bP411c7oJ/?spm_id_from=333.1387.homepage.video_card.click&vd_source=5cfd1b04987819146fefc856af2954b1)\n",
    "\n",
    "代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "87c1c06c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "def twoSum(numbers: List[int], target: int) -> List[int]:\n",
    "    numbers.sort()  # 修复：使用正确的排序方法\n",
    "    left = 0\n",
    "    right = len(numbers) - 1\n",
    "    while left < right:\n",
    "        sum = numbers[left] + numbers[right]\n",
    "        if sum == target:\n",
    "            return [left + 1, right + 1]  # 题目要求下标从1开始\n",
    "        elif sum < target:\n",
    "            left += 1\n",
    "        else:\n",
    "            right -= 1\n",
    "\n",
    "\n",
    "numbers = [2, 3, 4, 5, 8, 9]\n",
    "target = 7\n",
    "res = twoSum(numbers, target)\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6a6bcc6",
   "metadata": {},
   "source": [
    "# 2. 三数之和\n",
    "\n",
    "> 给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请你返回所有和为 `0` 且不重复的三元组。\n",
    ">\n",
    "> ```\n",
    "> 输入：nums = [-1,0,1,2,-1,-4]\n",
    "> 输出：[[-1,-1,2],[-1,0,1]]\n",
    "> 解释：\n",
    "> nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。\n",
    "> nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。\n",
    "> nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。\n",
    "> 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。\n",
    "> 注意，输出的顺序和三元组的顺序并不重要。\n",
    "> ```\n",
    "\n",
    "三数之和本质上和两数之和是一个道理，因为`nums[i] + nums[j] + nums[k] == 0`，所以`nums[i] + nums[j] = - nums[k]`。故只需要对`nums[k]`进行枚举，然后对每一个枚举的值使用两数之和的方法。\n",
    "\n",
    "另外操作：\n",
    "\n",
    "- 为了使用两数之和的方法，应该先对数组进行排序\n",
    "\n",
    "- 题目要求答案中不能有重复的三元组。如何避免重复？\n",
    "\n",
    "  - 在外层循环中，如果发现 `nums[k]=nums[k−1]`，那么 `nums[k]` 与后面两个数组成的和为 0 的三元组，`nums[k−1]` 也能组成一模一样的三元组，这就重复了，所以遇到 `nums[k]=nums[k−1]` 的情况，直接 continue。\n",
    "\n",
    "    > 假设 `nums = [-4, -1, -1, 0, 1, 2]`，固定`nums[k]`，剩下两个数相加`nums[i] + nums[j] = -nums[k]`，所以，只要`nums[k]`比如说等于-4固定，那剩下的两个数的和一定是-4。所以，为了避免重复，成为过`num[k]`的数就不能被再次访问了。所以，每次的`left`都应该从`k`的右边开始夹逼。\n",
    "\n",
    "  - 在内层循环中，当三数之和等于 0 时，为避免把相同的三元组计入答案，跳过后续相同的 `nums[left]` 和 `nums[right]`。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "dd02923f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 3, -4], [2, 2, -4], [-1, 2, -1]]\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums = sorted(nums)\n",
    "        ret = []\n",
    "        for k, num_k in enumerate(nums):\n",
    "            left = k+1\n",
    "            right = len(nums)-1\n",
    "            # 跳过重复的nums[k]\n",
    "            if k > 0 and nums[k] == nums[k-1]:\n",
    "                k += 1\n",
    "                continue\n",
    "            while left < right:\n",
    "                sum = nums[left] + nums[right]\n",
    "                # 和为0的情况应该避免重复\n",
    "                if sum == -num_k:\n",
    "                    ret.append([nums[left], nums[right], num_k])\n",
    "                    left += 1\n",
    "                    while left < right and nums[left] == nums[left - 1]:\n",
    "                        left += 1\n",
    "                    right -= 1\n",
    "                    while right > left and nums[right] == nums[right + 1]:\n",
    "                        right -= 1\n",
    "                    k += 1\n",
    "                elif sum < -num_k:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "        return ret\n",
    "\n",
    "\n",
    "sol = Solution()\n",
    "res = sol.threeSum([2, 3, -1, 7, 9, -4, -1, 1, 2])\n",
    "print(res)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "tmp",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.23"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
